package _05_stack.my_implements.exerc;

import _05_stack.Stack;
import _05_stack.my_implements.LinkedListStack;
import org.junit.Test;

import java.util.HashMap;

/**
 * @author: mornd
 * @dateTime: 2023/6/6 - 18:49
 * 有效的括号测试，给定一个只能包含"(", ")", "{", "}", "[", "]"的字符串，验证该字符串是否有效
 */
public class ValidSignTest {
    static final HashMap<Character, Character> signs;
    static {
        signs = new HashMap<>(4);
        signs.put('(', ')');
        signs.put('[', ']');
        signs.put('{', '}');
        signs.put('<', '>');
    }

    @Test
    public void test2() {
    }

    /**
     * 有效的括号测试，给定一个只能包含(){}[]的字符串，验证该字符串是否有效
     * 有效：[]
     *      ()[]
     *      ([])
     *
     * 无效：[
     *      ([)
     *      ([)]
     *      )(
     */
    @Test
    public void test() {
        String[] arr = {
                "[]",
                "((",
                "][",
                "([{}])",
                "()[]",
                "([)",
                "({)}"};

        for (int i = 0; i < arr.length; i++) {
            boolean valid = isValid(arr[i]);
            System.out.println(valid);
        }
    }

    /**
     * 思路：
     *      遍历字符，首先保证先遍历到的是左半部分括号
     *      然后将该左半部分对应的右部分压栈，然后继续遍历，如果仍是左半部分的括号则继续压栈右半部分
     *      如果遍历到了右半部分，则查看栈顶元素是否是符合左部分的符号，不符合直接返回false，符合则弹栈（弹出并删除），继续下一层遍历
     *
     *      ([
     *
     *       底 -> 顶
     *             )]
     * @param str
     * @return
     */
    boolean isValid(String str) { // string == char
        if(str == null || str.length() == 1) {
            return false;
        }
        Stack<Character> stack = new LinkedListStack<>();
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            if(signs.containsKey(c)) {
                stack.push(signs.get(c));
            } else {
                if(!stack.isEmpty() && stack.peek().equals(c)) {
                    stack.pop();
                } else {
                    return false;
                }

            }
        }
        return stack.isEmpty();
    }

    boolean isValid2(String str) {
        if(str == null) return false;
        Stack<Character> stack = new LinkedListStack<>();
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            if(signs.containsValue(c)) { // 先出现的右侧符号
                if(stack.isEmpty()) {
                    return false;
                } else {
                    if(c == stack.peek()) { // 与栈中相同即表示符号正确
                        stack.pop();
                        continue;
                    } else {
                        return false;
                    }
                }
            }
            if(signs.containsKey(c)) {
                stack.push(signs.get(c));
            }
        }
        return stack.isEmpty();
    }
}
